The present invention relates to encryption and decryption devices for use in public-key cryptosystems and a recording medium with their processing programs recorded thereon.
In the transmission and reception of data over a security-free communication channel, cryptosystems are used to guard against wiretapping. In general, cryptosystems fall into two categories: common-key cryptosystem and public-key cryptosystem. In the common-key cryptosystem, encipher and decipher keys are the same, and hence they need to be delivered in secrecy. Furthermore, since this technique requires as many keys as combinations of communication, an increase in the number of sending/receiving stations in the network inevitably causes an increase in the number of keys that must be kept secret.
On the other hand, the public-key cryptosystem uses different keys as encipher and decipher keys. Even if the encipher key is made public, the secrecy of the decipher key could be maintained as long as its computation from the encipher key is infeasible in terms of computational complexity. Accordingly, no delivery of the encipher key is necessary. Moreover, since each sending/receiving station needs only to keep its own decipher key in secrecy, it is also possible to solve the problem of the keys to be held secret. That is, the public-key cryptosystem offers a solution to the problem of key management encountered in the common-key cryptosystem. Another advantage of the public-key cryptosystem over the common-key cryptosystem is the settlement of the problem of key delivery which is the greatest difficulty with the latter; the former does not involve the secret key delivery. Besides, in public-key cryptosystem the same key is shared by the persons concerned, it is impossible to identify which person generated a ciphertext using the common key. With the public-key cryptosystem, however, since each person has his own secret key exclusively, it is possible to identify the person who generated a ciphertext using the secret key. Digital signature schemes utilize this property of public-key cryptosystem.
That is, the use of public-key cryptosystem permits the implementation of digital signature schemes, and ensures verification of the opponent of communication. It is well-known in the art that the public-key cryptosystem can be implemented through utilization of what is called a trapdoor one-way function. A one-way function is one that allows ease in computation in one direction but makes computation in the opposite direction infeasible in terms of computational complexity. The trapdoor one-way function mentioned herein is a one-way function with a trick xe2x80x9cknowledge of some secret allows ease in computation in the opposite direction as well.xe2x80x9d The trick is called a xe2x80x9ctrapdoor.xe2x80x9d
At present, there are known such yet-to-be-solved problems as listed below.
(a) Integer Factorization Problem (hereinafter referred to as IFP): A problem of factoring an input composite number into its prime factors;
(b) Discrete Logarithm Problem of Multiplicative Group over Finite Field (hereinafter referred to as DLP): A problem of determining, for example, an integer x in y=gx satisfying 0xe2x89xa6xxe2x89xa6p for a given element y in a multiplicative group Fp*= less than g greater than of a finite field Fp, where p is a prime;
(c) Discrete Logarithm Problem of elliptic curves over Finite Field (hereinafter referred to as ECDLP): A problem of determining, for example, an integer m satisfying P=mG for a point P in a subgroup of E(Fp) generated from a point G in a group E(Fp) composed of the entire Fp-points on an elliptic curve defined over the finite field Fp.
For the elliptic curve and elliptic curve cryptosystems, see, for example, Menezes, A. J., xe2x80x9cElliptic Curve Public Key Cryptosystems,xe2x80x9d Kluwer Academic Publishers (1993) (hereinafter referred to as Literature 1). The cryptosystems described in this literature are typical examples expected to use the one-way function. Typical and practical ones of public-key cryptosystems proposed at present are, for instance, the RSA cryptosystem, the Rabin cryptosystem, the ElGamal cryptosystem, and the elliptic curve cryptosystem (elliptic ElGamal cryptosystem). The RSA and Rabin cryptosystems are based on the intractability of IFP, the ElGamal cryptosystem is based on the intractability of DLP, and the elliptic curve cryptosystem is an Elgamal cryptosystem in a group of points on an elliptic curve over a finite field, which is based on the intractability of ECDLP.
The RSA cryptosystem is disclosed in Rivest, R. L. et al xe2x80x9cA Method for Obtaining digital Signatures and Public-Key Cryptosystems,xe2x80x9d Communication of the ACM, vol. 21, pp. 120-126 (1978) (hereinafter referred to as Literature 2). The Rabin cryptosystem is disclosed in Rabin, M. O. xe2x80x9cDigital signatures and Public-Key Functions as in tractable as Factorization,xe2x80x9d MIT, Technical Report, MIT/LSC/TR-212 (1979) (hereinafter referred to as Literature 3). The ElGamal cryptosystem is disclosed in ElGamal, T. xe2x80x9cA Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,xe2x80x9d IEEE Trans. on Information Theory, IT-31, 4, pp. 469-472 (1985) (hereinafter referred to as Literature 4). The elliptic curve cryptosystem was proposed by Miller, V. S. and Kolblitz, N. separately in 1985, and this scheme is described in Miller, V. S. xe2x80x9cUse of Elliptic Curves in Cryptography,xe2x80x9d Proc. of Crypto ""85, LCNCS 218, springer-Verlag, pp. 417-426 (1985) (hereinafter referred to as Literature 5) and in Kolblitz, N., xe2x80x9cElliptic Curve Cryptosystems,xe2x80x9d Math. Comp., 48, 177, pp. 203-209 (1987) (hereinafter referred to as Literature 6).
Now, the above-mentioned cryptosystems and their properties will be described concretely.
A description will be given first of how the RSA cryptosystem is constructed. Let p and q be odd primes and choose n, e and d such that they satisfy the following equations:
n=pq
GCD(e, LCM(pxe2x88x921, qxe2x88x921))=1
edxe2x89xa11 (mod LCM(pxe2x88x921, qxe2x88x921))
where GCD(a, b) is the greatest common divisor of integers a and b, and LCM(a, b) is the least common multiple of the integers a and b.
The encryption and decryption processes E(M) and D(C) of a message M are defined by the following equations using (n, e) as public keys and (d, p, q) as secret keys.
Cxe2x89xa1E(M)xe2x89xa1Me (mod n)xe2x80x83xe2x80x83(1)
Mxe2x89xa1D(C)xe2x89xa1Cd (mod n)xe2x80x83xe2x80x83(2)
At this time, if M satisfies 0xe2x89xa6Mxe2x89xa6nxe2x88x921, then the following equation holds.
D(E(M))=Mxe2x80x83xe2x80x83(3)
The Rabin cryptosystem is constructed as follows: Choose p, q and n in the same manner as in the above, and determine the integer b which satisfies 0bn. The encryption process E(M) and the description process D(c) are defined by the following equations using (n, b) as public keys and (p, q) as secret keys.                     C        ≡                  E          ⁡                      (            M            )                          ≡                              M            ⁡                          (                              M                +                b                            )                                ⁢                      xe2x80x83                    ⁢                      (                          mod              ⁢                              xe2x80x83                            ⁢              n                        )                                              (        4        )                                                                    M              ≡                              xe2x80x83                            ⁢                              D                ⁡                                  (                  C                  )                                            ≡                                                                    (                                                                  -                        b                                            ±                                                                        (                                                                                    b                              2                                                        +                                                          4                              ⁢                              C                                                                                )                                                                          1                          /                          2                                                                                      )                                    /                  2                                ⁢                                  xe2x80x83                                ⁢                                  (                                      mod                    ⁢                                          xe2x80x83                                        ⁢                    p                                    )                                                                                                        ≡                              xe2x80x83                            ⁢                                                                    (                                                                  -                        b                                            ±                                                                        (                                                                                    b                              2                                                        +                                                          4                              ⁢                              C                                                                                )                                                                          1                          /                          2                                                                                      )                                    /                  2                                ⁢                                  xe2x80x83                                ⁢                                  (                                      mod                    ⁢                                          xe2x80x83                                        ⁢                    q                                    )                                                                                        (        5        )            
The Rabin cryptosystem involves solving simultaneous equations in decryption, but since the quadratic equation possesses two solutions, the calculation in this case brings about four solutions, giving rise to a problem that the decryption cannot uniquely be performed under the above conditions. This can be settled as a problem of system operation by using some additional information for communication; and the Rabin cryptosystem has also been improved for unique description. This is described in Kaoru Krosawa et al., xe2x80x9cPublic-Key Cryptosystems Using Reciprocals which are as Intractable as Factoring,xe2x80x9d Journal of IEICE, Vol. J70-A, No. 11, pp. 1632-1636 (1987) (hereinafter referred as to Literature 7).
The ElGamal cryptosystem is constructed as follows: Let p be a prime. Choose g as one generating element of a modular-p reduced residue class group (Z/pZ)*, that is, as an element of the order p. Choose an integer x such that 0 less than x less than p, and set yxe2x89xa1gx(mod p). The encryption process E(M) and the decryption process D(C) are defined by the following equations using (y, g, p) as public keys and x as a secret key.
C=(C1, C2)=E(M)xe2x80x83xe2x80x83(6)
C1xe2x89xa1gr(mod p)xe2x80x83xe2x80x83(7)
C2xe2x89xa1yrM(mod p)xe2x80x83xe2x80x83(8)
Mxe2x89xa1D(C)C2/C1x mod pxe2x80x83xe2x80x83(9)
where r is an arbitrary integer such that 0 less than r less than p, which is chosen for each encryption.
If M is 0 less than M less than p, then the following equation holds.
M=D(E(M))xe2x80x83xe2x80x83(10)
The elliptic curve cryptosystem (elliptic ElGamal cryptosystem) is constructed as follows: Let p be a prime and define the elliptic curve over a finite field Fp as follows:
E(a, b): y2=x3+ax+b
where a, bxcex5Fp, and 4a3+27b2xe2x89xa00
Choose an Fp-rational point G on the elliptic curve such that its order q has a sufficiently large prime as the divisor. Choose an arbitrary integer x such that 0 less than x less than q, and let P=xG by addition on the elliptic curve E(a, b). Then, the encryption process E(M) and the decryption process D(C) are defined by the following equations using {p, E(a, b), G, P, q} as public keys and x as a secret key.
C=(C1, C2)=E(M)xe2x80x83xe2x80x83(11)
C1=rG1xe2x80x83xe2x80x83(12)
C2=rP+Mxe2x80x83xe2x80x83(13)
xe2x80x83M=D(C)=(C2xe2x88x92xC1); x-cordinatexe2x80x83xe2x80x83(14)
where r is an arbitrary integer which satisfies 0 less than r less than q, and is chosen for each encryption and rP+M is the sum, on the elliptic curve, of a point which has M on the X-coordinate and a point rp on the elliptic curve. In general, it is not known whether there is always present on a given elliptic curve the point which has M on the X-coordinate (In this case, the point exists with a probability of 1/2). If a rule common to systems is established to add redundant information to M to some extent, it will be possible to always obtain the point which has, on the X-coordinate, M added with redundant information.
Next, a description will be given of the computational complexity of each cryptosystem mentioned above. As regards the RSA cryptosystem, it is well-known that the computational complexities for both of the encryption and the decryption are on the order of k3, where k is the number of bits of the public key n. In the Rabin cryptosystem, the computational complexity is on the order k2 for encryption and on the order of k3 for decryption. In this case, too, k represents the number of bits of the public key n.
In the ElGamal cryptosystem, the computational complexity is on the order of k3 for each of the encryption and the decryption, where k represents the number of bits of the prime p used as the public key.
The computational complexities of the above cryptosystems do not so much differ in terms of order, but it is evident that when they are implemented, their computational complexities will much differ. Actually it is well-known that the addition on the elliptic curve takes time about ten times longer than does multiplication in the finite field over which the elliptic curve is defined.
Next, the security of the above cryptosystems will be described.
Since the cryptosystems are intended to send messages in the form of ciphertexts to conceal the message contents from adversaries (wiretappers), it is of importance the extent to which the message contents are concealed. That is, the intractability of cryptoanalysis falls into full or complete analysis or decryption (means that the original plaintext is fully decrypted from the ciphertext) and fractional analysis (which means that fractional information of the plaintext is decrypted from the ciphertext). Attacks on the public-key cryptosystems are divided into two types: (a) passive attacks which merely receive an encrypted message and try to decrypt or analyze its contents only from the received information, and (b) active attacks which are allowed to send various challenges or questions (in ciphertext form) to the sending party and receive responses thereto (the results of decryption of the ciphertext) and analyze or decrypt the aimed ciphertext based on the information received from the sending party. Of the active attacks, an adaptive chosen ciphertext attack (an attack that the cryptoanalyst causes his arbitrarily chosen ciphertext to be decrypted by the true receiving part and then decrypts another ciphertext through utilization of the thus obtained information and public information is the most powerful.
Now, the security of the typical public-key cryptosystems will be described based on the classifications referred to above. In the cryptosystems based on the intractability of the IF (Integer Factoring) problem, such as the RSA and Rabin cryptosystems, if the public key n can be factored, then the primes p and q which constitute the secret key can be detected and the least common multiple LCM(pxe2x88x921, qxe2x88x921) can be computed, by which the secret key d is obtained. Hence, these cryptosystems are subject to full or complete analysis. It has been proven that the computation of LCM(pxe2x88x921, qxe2x88x921) solely from n is equivalent to the factoring of the latter. That is, LCM(pxe2x88x921, qxe2x88x921) cannot be obtained unless the primes p and q are known.
The RSA cryptosystem may be completely be analyzed by a method other than that of factoring the public key n into a prime factor, but it has been proven that only the factoring of the public key n is effective in complete analysis of the Rabin cryptosystem. That is, although it is still unknown whether the analysis of the RSA cryptosystem is equivalent to solving the IF problem, it has been proved that complete analysis of the Rabin cryptosystem is equivalent to solving the IF problem. The same is true of an inverse version of the Rabin cryptosystem. This finding on the Rabin cryptosystem has demonstrated for the first time that a certain kind of security of the cryptosystem can be proved by the assumption of the intractability of a basic problem (the IF problem in this case). This means that the security of above-described public-key cryptosystems against the passive attacks has been proved on the assumption of the intractability of the IF problem. Conversely, this is a proof that the Rabin cryptosystem is weak against the active attacks. An efficient cryptosystem, which is secure against the chosen ciphertext attack, is disclosed, for example, in Bellare et al., xe2x80x9cOptimal Asymmetric Encryption,xe2x80x9d Proc. of Eurocrypt 194, LCNCS 950, Springer-Verlag, pp. 92-111, 1995 (hereinafter referred to as Literature 8).
As regards fractional or partial cryptoanalysis, it has been proved on the RSA and Rabin cryptosystem that the computation of the least significant bit of the plaintext M from the ciphertext is as difficult as the computation of the whole plaintext M from the ciphertext C. It has also been proved that the portion of the plaintext corresponding to log k bits continuing from its least significant bit possesses similar security. This is described in Alexi, W. et al., xe2x80x9cRSA and Rabin functions: certain parts Are as Hard as the Whole,xe2x80x9d SIAM Journal of computing, 17, 2, pp. 449-457 (1988) (hereinafter referred to as Literature 9).
The ElGamal cryptosystem is based on the intractability of DLP (the discrete logarithm problem); hence, if DLP can be solved, then the secret key x is available from the public key (y, g, p), permitting the analysis of the cryptosystem. However, it has not been proved whether the analysis of the ElGamal cryptosystem is as hard as DLP. As for the elliptic cryptosystem, too, it has not been proved whether its analysis is as hard as ECDLP (the problem of the discrete logarithm on the elliptic curve).
As described above, the public-key cryptosystems solves the key management problem raised in the conventional common-key cryptosystem, and permit implementation of digital signature schemes. However, the public-key cryptosystems, for which a certain kind of security can be proved by assuming the intractability of the basic problem are limited only to the Rain cryptosystem and its modifications. That is, actually usable one-way functions are only IFP, DLP and ECDLP. No provably secure public-key cryptosystem has been implemented which uses a new xe2x80x9ctrapdoorxe2x80x9d based on such a known one-way function.
It is therefore an object of the present invention to provide encryption and decryption devices for public-key cryptosystems which use IFP as a one-way function but uses a new xe2x80x9ctrapdoorxe2x80x9d and which can be proved to be secure against passive adversaries based on the assumption that IFP is intractable.
Another object of the present invention is to provide a recording medium on which there are recorded encryption and decryption programs of the encryption and decryption devices for public-key cryptosystems.
The encryption device according to the present invention comprises: exponent generation means for combining an input plaintext m and a random number r to generate an exponent; and exponentiating means for generating a ciphertext by exponentiating a second public key g with the exponent in a modular-n reduced residue class group, where n is a first public key which is a composite number.
The decryption device according to the present invention comprises: xcex93-transform means for transforming an input ciphertext, by using a first secret key, to an element Cp of a modular-n reduced residue class group, where n is the first public key which is a composite number; and discrete logarithm solution means for solving a discrete logarithm in the transformed element Cp through the use of a second secret key.